package com.ww.springboot.boot.algorithm.dp.study;

/**
 * 描述：
 * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
 *
 * 每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
 *
 * 请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
 *
 * F(n) = F(n-1)+arg[n] or F(n-2)+arg[n]
 *
 * F(1) =  0     可以直接两步跨过
 * F(2) =  15    比较arg[1] arg[2]的值 取小的
 * F(3) =        取 F(2) + arg[2]  F(1) +arg[1] 较小的
 * F(n) = min(F(n-2) + arg[n-1], F(n-1) + arg[n])
 *
 * 解法:(添加一条辅助线)
 *    到达i阶梯有两种方式:1 踏上i-1阶梯
 *
 *
 * @author wanwei
 * @since 2021-11-08 15:53
 */
public class MinCostClimbingStairs3 {


    public static void main(String[] args) {
        int[] cost = {1,100,1,1,1,100,1,1,100,1};
        System.out.println(minCostClimbingStairs2(cost));
        int[] cost2 = {1,100,1,1,1,100,1,1,100,1};
        System.out.println(minCostClimbingStairs(cost2));
    }

    public static int minCostClimbingStairs(int[] cost) {
        int one = 0;
        int two = Math.min(cost[0], cost[1]);
        for(int i =2 ;i<cost.length;i++){
            int next = Math.min(two+cost[i],one+cost[i-1]);
            one = two;
            two = next;
        }
        return two;
    }

    public static int minCostClimbingStairs2(int[] cost) {
        int size = cost.length;
        int[] minCost = new int[size];
        minCost[0] = 0;
        minCost[1] = Math.min(cost[0], cost[1]);
        for (int i = 2; i < size; i++) {
            minCost[i] = Math.min(minCost[i - 1] + cost[i], minCost[i - 2] + cost[i - 1]);
        }
        return minCost[size - 1];
    }


}
